//https://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f?tpId=13&tqId=2290592&ru=%2Fpractice%2Fe0cc33a83afe4530bcec46eba3325116&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//问题：这个问题还不错，利用二叉搜索树的性质，左子树<中心节点<右子树；（必须掌握）
//思路：1.递归遍历；
//     2.while 循环判断；

#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <stack> 
#include <limits>

using namespace std;
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        //空树找不到公共祖先
        if(root == nullptr) 
            return -1;
        
        while(true) {
            if((p >= root->val && q <= root->val) || (p <= root->val && q >= root->val))  {
                break;
            }
            if(p < root->val && q < root->val) {
                root = root->left;
                
            }
            if (p > root->val && q > root->val) {
                root = root->right;
            }
            if (root == nullptr) return -1;
        }
        return root->val; 
    }
};

class Solution {
public:
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        //空树找不到公共祖先
        if(root == NULL)
            return -1;
        //pq在该节点两边说明这就是最近公共祖先
        if((p >= root->val && q <= root->val) || (p <= root->val && q >= root->val))
            return root->val;
        //pq都在该节点的左边
        else if(p <= root->val && q <= root->val)
            //进入左子树
            return lowestCommonAncestor(root->left, p, q);
        //pq都在该节点的右边
        else
            //进入右子树
            return lowestCommonAncestor(root->right, p, q);
    }
};
